/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2501.java
 * @Author : WangRuoyu
 * @Date 2022/12/17 9:38
 */

package leetcode;

import java.util.Arrays;
import java.util.HashSet;

public class Q2501 {
    /*** 线性动态规划 ***/
//    public int longestSquareStreak(int[] nums) {
//        int res = -1;
//        Arrays.sort(nums);
//        int m = nums.length;
//        int maxvalue = nums[m - 1];
//        int[] index = new int[maxvalue + 10];
//
//        for (int i = m - 1; i >= 0; i--) {
//            long y = (long) (nums[i] * nums[i]);
//            if (y < (maxvalue + 10)) {
//                index[nums[i]] = index[(int) y] + 1;
//            } else {
//                index[nums[i]] = 1;
//            }
//            res = Math.max(res, index[nums[i]]);
//        }
//
//        if (res < 2) {
//            res = -1;
//        }
//
//        return res;
//    }

    /*** 哈希表 ***/
//    public int longestSquareStreak(int[] nums) {
//        int res = -1;
//        HashSet<Long> set = new HashSet<>();
//        int m = nums.length;
//        int maxvalue = -1;
//
//        for (int i = 0; i < m; i++) {
//            set.add((long) (nums[i]));
//            if (maxvalue < nums[i]) {
//                maxvalue = nums[i];
//            }
//        }
//
//        for (int i = 0; i < m; i++) {
//            int len = 1;
//            long num = nums[i];
//            while (((num * num) <= maxvalue) && (set.contains(num * num))) {
//                len++;
//                num *= num;
//            }
//            if ((len >= 2) && (res < len)) {
//                res = len;
//            }
//        }
//        return res;
//    }

    /*** 数组 ***/
    public int longestSquareStreak(int[] nums) {
        int res = -1;
        Arrays.sort(nums);
        int m = nums.length;
        int maxvalue = nums[m - 1];
        int[] index = new int[maxvalue + 1];

        for (int i = 0; i < m; i++) {
            index[nums[i]] = 1;
        }

        for (int i = 0; i < m; i++) {
            int len = 1;
            int num = nums[i];
            while (((num <= 320) && (num * num) <= maxvalue) && (index[num * num] == 1)) {
                len++;
                num *= num;
            }
            if ((len >= 2) && (res < len)) {
                res = len;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Q2501 sl = new Q2501();
        int[] nums = {4, 3, 6, 16, 8, 2};
        System.out.println(sl.longestSquareStreak(nums));
    }
}